//
// Created by Dell on 2021/11/23.
//

#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;

int Partition(int A[],int left ,int right){
    int p = (round(1.0*rand()/RAND_MAX*(right-left)+left));
    swap(A[p],A[left]); // 随机选择主元 时间复杂度降到nlogn
    int temp = A[left];
    while(left<right){
        while(left<right&&A[right]>temp) right--;
        A[left] = A[right];
        while(left<right&&A[left]<temp) ++left;
        A[right] = A[left];
    }
    A[left] = temp;
    return left;
}

void QuickSort(int A[],int left,int right){
    if(left<right){
        int pos = Partition(A,left,right);
        QuickSort(A,left,pos-1);
        QuickSort(A,pos+1,right);
    }
}

int main(){
    srand((unsigned )time(NULL));
    int a[] = {5,6,9,564,216,1,35};
    QuickSort(a,0,6);
    for(int i = 0;i<7;++i){
        printf("%d ",a[i]);
    }
}